The present invention relates to techniques for decoding data in digital communication systems. More specifically, the present invention relates to an improved technique for decoding convolutional encoded data by using the Viterbi algorithm.
Digital communication systems, such as digital radios, mobile phones, satellite links and bluetooth implementation, employ numerous coding techniques for transmitting data through noisy communication channels. These coding techniques enhance the noise immunity of the original data during the transmission. One such coding technique is ‘convolutional coding’. The convolutional coding technique encodes an m-bit data to an n-bit data, where m is less than n, and then transmits the n-bit data to a receiver. To recover the original data with the receiver, the convolutional encoded data is decoded by using various decoding techniques.
One of the decoding techniques for the convolutional encoded data is Viterbi decoding. The Viterbi decoding provides a high degree of likelihood that the original data corresponds to the encoded data received. This technique involves the generation of possible data sequences that are estimates of the original data. A data sequence that is closest to the original data is selected from the possible data sequences, on the basis of certain predefined parametric conditions. The selected data sequence can then be decoded.
The Viterbi decoding algorithm involves locating a common path at every instant in a trellis. The trellis is a state diagram that includes different states at various time instants, which are represented as nodes. An example of the trellis is shown in FIG. 2. Trace back is performed from all the nodes at every instant to locate a common path. Once the common path is obtained, the selected data sequence at the node is decoded. If a common path is not obtained at a particular instant, the next time instant is traced back to locate a common path. This trace-back decoding method results in variable latencies at different time instants. Problems related to variable latency can be resolved by starting decoding of the bits after a sufficient number of time instants are completed. The number of time instants completed in the trellis before the starting of the decoding process is known as the trace-back depth. Several resources, such as registers, comparators, adders and other electronic circuits, are used to trace back the maximum likelihood path. Therefore, the trace-back depth needs to be selected in such a way that decoding of data sequences is achieved with the minimal use of the resources required for decoding, with there being no significant deterioration in performance. The probability of all the possible paths having identical decoded data sequences increases with an increase in the trace-back depth.
There are different methods for tracing back in the trellis to decode convolutional encoded data. Two such methods include the fixed node method and the minimum metric node method. In the fixed node method, the trace-back depth is selected for a large number of time instants, to decode a data sequence. However, an increase in the trace-back depth increases decoding latency and the resources required to store the information bits corresponding to the common path. On the other hand, the minimum metric node method selects a node with the minimum metric value. The metric value is an accumulation of a predefined parametric value for each branch in the path. Finding the minimum metric node reduces the trace-back depth, and hence, the need for the resources required to store the possible paths. However, additional resources such as comparators are needed to locate the node with the minimum metric value.
Therefore, there exists a need for a method for reducing the trace-back depth to conserve resources. Additionally, a need exists for a method for performing decoding with minimum latency, without using comparators. There also exists a need for the low complexity implementation of a Viterbi Decoder with near optimal performance.